Methods for performing searches of encrypted data that do not compromise the confidentiality of the encrypted data are known to the art. For example, in one common configuration a server computing device stores a large number of encrypted data files with an associated encrypted search index. One or more client computing devices make search requests to the server using encrypted representations of search keyword terms. Symmetric Searchable Encryption (SSE) is one method for performing searches in an encrypted search index that enables a client computing device that has access to a symmetric cryptographic key to perform searches for specific terms in the encrypted search index that is stored on the server. The server, however, only receives the encrypted search terms and cannot identify the content of the search terms based on the communications that are received from the client because the server does not have access to the (secret) cryptographic key required to decrypt the search terms.
Existing searchable encryption systems enable a client to search for a specific term or “keyword” in an encrypted search index. However, many searches that occur in practical systems perform searches within a range of values, and the prior art encrypted search schemes do not perform range searches efficiently. For example, a prior art encrypted search system can effectively search for the number 5,000 in an encrypted search index, but searching for a range of numbers such as 2,500 to 10,000 (inclusive) is an inefficient process since the client must perform 7,501 individual search operations (assuming only integer values) to fully cover the search range. The nature of the encrypted search index prevents the server from performing an efficient ranged search operation that would be used in a traditional search engine or database because doing so would compromise the confidentiality of the encrypted files that are stored on the server. Consequently, improvements to methods and systems for performing searches in encrypted data over a range of values would be beneficial.